#include <string>
#include <algorithm>

using namespace std;

class Solution
{
public:
    string addBinary(string a, string b)
    {
        string ret;
        auto abegin = a.rbegin(), bbegin = b.rbegin();
        int num = 0;
        while (abegin != a.rend() && bbegin != b.rend())
        {
            num = *abegin - '0' + *bbegin - '0' + num;
            ret.push_back(num % 2 + '0');
            num /= 2;
            ++abegin;
            ++bbegin;
        }

        while (abegin != a.rend() )
        {
            num = *abegin - '0' + num;
            ret.push_back(num % 2 + '0');
            num /= 2;
            abegin++;
        }

        while (bbegin != b.rend() )
        {
            num = *bbegin - '0' + num;
            ret.push_back(num % 2 + '0');
            num /= 2;
            bbegin++;
        }
        
        if (num)
        {
            ret.push_back('1');
        }

        reverse(ret.begin(), ret.end());
        return ret;
    }
};